# coding: utf-8
from google.appengine.ext import webapp
from google.appengine.ext.webapp.util import run_wsgi_app

import copy, math, models, pickle

MAX_PATH_LEN = 20

def get_map():
    dbMap = models.BinaryData.get_by_key_name('map')
    map = dbMap.data
    map = pickle.loads(map)
    return map

def get_nearest_station(stations, lat, lon):
    def get_len(station):
        res = math.sqrt(math.pow(station['lat'] - lat, 2) + math.pow(station['lon']-lon, 2))
        return res
    
    min_len = get_len(stations.values()[0])
    min_station = stations.values()[0]
    for station in stations.values():
        cur_len = get_len(station)
        if cur_len < min_len:
            min_len = cur_len
            min_station = station
    
    return min_station

def get_nearest_stations(stations, lat, lon, count):
        res_stations = []
        for station in stations.values():            
            current_len = math.sqrt(math.pow(station['lat'] - lat, 2) + math.pow(station['lon']-lon, 2))
            res_stations.append({'id' : station['id'], 'name' : station['name'], 'len' : current_len, 'lat' : station['lat'], 'lon' : station['lon']})
            
        res_stations.sort(key=lambda st:st['len'])
        
        res_stations = res_stations[:count]
        return res_stations

def get_routes(stations, start_id, end_id):
    routes = []
    path = [] # {'route': id, 'station' : id}
    if start_id == end_id:
        return []
    
    def try_path(current_id):
        path.append(current_id)
        if current_id == end_id:
            routes.append(copy.copy(path))
        elif len(path) == MAX_PATH_LEN:
            pass
        else:
            for next_station_id in stations[current_id]['next_stations']:
                try_path(next_station_id)
        path.pop()

    try_path(start_id)
    
    def add_bus_numbers(route):
        for i in xrange(len(route)-1):
            current_id = route[i]
            next_id = route[i+1]
            bus_ids = []
            
            current_station_bus_ids = []
            for next_station_info in stations[current_id]['next_stations'][next_id]:
                bus_ids.append(next_station_info['route'])
            route[i] = {'route_ids' : bus_ids, 'station_id' : current_id}
            
        if len(route) > 1:
            route[len(route)-1] = {'route_ids' : route[len(route)-2]['route_ids'], 'station_id' : route[len(route)-1]}
        
    for route in routes:
        add_bus_numbers(route)
    
    
    def get_buses(station_id):
        """id маршрутов, на которых можно ехать от данной станции"""
        buses = {}
        for route in routes:
            for station in route:
                try:
                    if station_id == station['station_id']:
                        for route_id in station['route_ids']:
                            buses[route_id] = 1
                except:
                    raise Exception(str(start_id + '|' + end_id))
    
        return buses.keys()
    
    def end_station(start_station_id, bus_id):
        """
        Возвращает максимальну станцию, до которой можно доехать на транспорте route_id двигаясь по одному из найденных маршрутов двигаясь от станции 
        start_id
        возвращает { 'station_id' : id }
        """
        end_station = None
        end_len = 0
        for route in routes:
            start = None
            for i in xrange(len(route)):
                if route[i]['station_id'] == start_station_id: 
                    start = i
                    break
                
            if start == None: continue
            
            end = None
            current_len = 0
            for i in xrange(start, len(route)-1):
                current_route = route[i]
                if bus_id in current_route['route_ids']:
                    end = i+1
                    current_len += 1
                else: break
            
            if current_len > end_len:
                end_station = route[end]['station_id']
                end_len = current_len
        return {'station_id' : end_station}
    
    buses_routes = []
    start_buses = get_buses(start_id)
    for bus in start_buses:
        bus_end = end_station(start_id, bus)
        buses_routes.append([{'start' : {'id' : start_id}, 'end' : {'id' : bus_end['station_id']}, 'route_id' : bus}])            
    
    calc_routes = True
    while calc_routes:
        calc_routes = False
        new_buses_routes = []        
        for bus_route in buses_routes:
            last = bus_route[len(bus_route)-1]
            if last['end']['id'] == end_id:
                new_buses_routes.append(bus_route) 
                continue
            calc_routes = True
            buses = get_buses(last['end']['id'])
            for bus in buses:
                start = last['end']['id']
                end = end_station(start, bus)
                new_route = copy.copy(bus_route)
                new_route.append({'start' : {'id' : start}, 'end' : {'id' : end['station_id']}, 'route_id' : bus})
                new_buses_routes.append(new_route)
        buses_routes = new_buses_routes
    

    for bus_route in buses_routes:
        for i in xrange(len(bus_route)):
            station = copy.copy(bus_route[i])
            bus_route[i] = station
            station['route_ids'] = [station['route_id']]
            del station['route_id']
    
    def add_alternative_routes(route1, route2):
        def drop_duplicates(arr):
            arr.sort()
            for i in reversed(xrange(len(arr)-1)):
                if arr[i] == arr[i+1]:
                    del arr[i+1]
        
        for step_1 in route1:
            for step_2 in route2:
                if step_1['start'] == step_2['start'] and step_1['end'] == step_2['end']:
                    step_1['route_ids'].extend(step_2['route_ids'])
                    step_2['route_ids'].extend(step_1['route_ids'])
                    drop_duplicates(step_1['route_ids'])
                    drop_duplicates(step_2['route_ids'])
    
    for i in xrange(len(buses_routes)-1):
        for k in xrange(i+1, len(buses_routes)):
            add_alternative_routes(buses_routes[i], buses_routes[k])
    
    # Удалить повторяющиеся маршруты
    for i in reversed(xrange(len(buses_routes))):
        if i >= len(buses_routes) : continue
        route = buses_routes[i]
        for k in reversed(xrange(i)):
            route2 = buses_routes[k]
            if route is route2: continue
            if route == route2: del buses_routes[k]
    
    # Отсортировать по пересадкам
    buses_routes.sort(key=lambda route: len(route))
    
    # Привести к формату вывода
    for i in xrange(len(buses_routes)):
        route = buses_routes[i]
        for station in route:
            station['start']['name'] = stations[station['start']['id']]['name']
            station['end']['name'] = stations[station['end']['id']]['name']
        buses_routes[i] = {'items' : buses_routes[i]}                        
    return buses_routes